package com.zhugang.week10;

/**
 * @program algorithms
 * @description: rob2
 * @author: chanzhugang
 * @create: 2022/08/30 16:06
 */
public class Rob2 {

    /**
     * 213 打家劫舍II
     *
     * @param nums
     * @return
     */
    public int rob2(int[] nums) {
        // 第一个房屋和最后一个房屋相邻（圆圈）
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        if (n == 2) {
            return Math.max(nums[0], nums[1]);
        }
        // 这里总的是n个房子，从0开始算起，所有总的是0到 n-1
        // 第0个不偷窃，偷窃 1 ~ n-1
        int max1 = rob_dp(nums, 1, n - 1);
        // 第0个偷（第一个和最后一个不偷）， 偷 2 ～ n-2
        int max2 = nums[0] + rob_dp(nums, 2, n - 2);
        return Math.max(max1, max2);
    }

    /**
     * 198 一样
     *
     * @param nums
     * @param p
     * @param r
     * @return
     */
    private int rob_dp(int[] nums, int p, int r) {
        // 和第一题一样
        int n = nums.length;
        int[][] dp = new int[n][2];
        dp[p][0] = 0;
        dp[p][1] = nums[p];

        for (int i = p + 1; i <= r; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = dp[i - 1][0] + nums[i];
        }
        return Math.max(dp[r][0], dp[r][1]);
    }
}